# 电话号码的字母组合: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        """
            每个组合的长度就是 digits 的长度
        """
        # 1. 求长度
        k = len(digits)
        # 2. 建立数字与字符的映射
        phone = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "stu",
            "9": "vwxy"
        }

        # 开始求解
        rst = []
        def getCmb(cmb, idx):
            """
                param:  cmb: 合并的字符串，达到k长返回
                param:  idx: 表示下标，遍历digits 的每一个字符数字
            """
            if len(cmb) == k:
                rst.append(cmb)
                return
            
            digit = digits[idx]
            s = phone.get(digit)
            for i in range(len(s)):
                getCmb(cmb + s[i], idx + 1)

        getCmb('', 0)    
        return rst

